package com.dyz.leetcode;

import sun.java2d.pipe.AAShapePipe;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum39 {
//    public static void main(String[] args) {
//        //candidates = [2,3,6,7], target = 7
//        int [] candidates = {2,3,6,7};
//        List<List<Integer>> lists = new CombinationSum39().combinationSum(candidates, 7);
//        System.out.println(lists);
//    }
//    //数组 回溯
//    private List<List<Integer>> list;
//
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        list = new ArrayList<>();
//        List<Integer> list1 = new ArrayList<>();
//        if(candidates==null||candidates.length==0||target<0){return list;}
//        //回溯
//        helper(target, 0, candidates, list1);
//
//        return list;
//    }
//
//    private void helper(int target, int index, int[] candidates, List<Integer> list1){
//        //终止条件
//        if(target==0){
//            list.add(new ArrayList<>(list1));
//            return;
//        }
//        if(target<0){
//            return;
//        }
//        for(int i=0; i<candidates.length; i++){
//            list1.add(candidates[i]);
//            helper(target-candidates[i], i, candidates, list1);
//            list1.remove(list1.size()-1);
//        }
//
//    }

    //数组 回溯
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }
}
